1. Field of the Invention
The present invention concerns switches used in communications networks. More specifically, the present invention concerns scheduling of packets sent through the switching fabric of such a switch.
2. Background Information
Internet traffic has increased drastically in recent years. Expected traffic demand will require future packet switching systems to switch packets in a very short time (just a few nanoseconds). Scheduling algorithms with lower computation complexity are desirable for such high-speed switching. Among the existing algorithms that may achieve 100% throughput for any admissible Bernoulli traffic, ALGO3 (See, e.g., the article, P. Giaccone, B. Prabhakar, and D. Shah, “Toward Simple, High Performance Schedulers for High-Aggregate Bandwidth Switches,” Proc. of IEEE INFOCOM, (New York, 2002), incorporated herein by reference.) and EMHW (See, e.g., the article, Y. Li, S. Panwar, and H. J. Chao, “Exhaustive Service Matching Algorithms for Input Queued Switches,” Proc. of IEEE HPSR (Phoenix, Ariz.) (April 2004), incorporated herein by reference.) have the lowest computational complexity, which is O(log N), where N is the number of ports in the switch.
The seminal work by Tassiulas and Ephremides (See, e.g., the article, L. Tassiulas and A. Ephremides, “Stability Properties of Constrained Queuing Systems and Scheduling Policies for Maximum Throughput in Multihop Radio Networks,” IEEE Transactions on Automatic Control, 37(12):1936-1949 (December 1992), incorporated herein by reference.) initiated the study of scheduling algorithms in packet switching systems and wireless networks. Maximum weight matching (MWM), which was proposed in the Tassiulas-Ephremides article, can stabilize the system whenever the arrival traffic is admissible Bernoulli i.i.d. However, the MWM algorithm may not be practical due to its O(N3) complexity.
A number of practical scheduling algorithms, such as iSLIP (See, e.g., the article, N. Mckeown, “The iSLIP Scheduling Algorithm for Input-Queued Switches,” IEEE/ACM Transactions on Networking, vol. 7, pp. 188-201 (April 1999), incorporated herein by reference.), iLQF (See, e.g., N. Mckeown, “Scheduling Algorithms for Input-queued Cell Switches,” Ph.D. Thesis, University of California at Berkeley, (1995), incorporated herein by reference.) and DRRM (See, e.g., the article, Y. Li, S. Panwar, and H. J. Chao, “On the Performance of a Dual Round-Robin Switch,” Proc. of IEEE INFOCOM (April 2001), incorporated herein by reference.), were proposed for real implementation. However, when the arriving traffic is non-uniform, these algorithms cannot achieve 100% throughput, and induce a higher delay as compared to the MWM algorithm.
A randomized scheduling algorithm with a linear complexity of O(N) was proposed by Tassiulas. (See, e.g., the article, L. Tassiulas, “Linear Complexity Algorithms for Maximum Throughput in Radio Networks and Input Queued Switches,” Proc. of IEEE INFOCOM, (New York), (1998), incorporated herein by reference.) The algorithm works as follows. Let S(n−1) represent the schedule at time n−1. At the beginning of time slot n, it randomly generates a schedule R(n), and then compare the weights of S(n−1) and R(n), where the weight of a schedule is defined as: W(S)=Σi,jSij×Qij. Then the new schedule is decided following the rule: S(n)=arg maxS∈[S(n−1), R(n)]W(S)
As can be seen, the algorithm uses the memory of the schedule in the previous time slot S(n−1). Therefore, it can reduce the computation complexity to O(N), and still achieve 100% throughput for any admissible Bernoulli traffic. However, its delay performance may be poor. Several algorithms were proposed by Giaccone et al. (See, e.g., the article, P. Giaccone, B. Prabhakar, and D. Shah, “Toward Simple, High Performance Schedulers for High-Aggregate Bandwidth Switches,” Proc. of IEEE INFOCOM, (New York, 2002), incorporated herein by reference.) to improve the delay performance. Giaccone et al. noted that instead of picking a schedule between S(n−1) and R(n), a new schedule can be generated by adding heavy edges from S(n−1) and R(n). This is referred as a “merge”. The new algorithm, which is called LAURA, can have a much better delay performance. SERENA, which also considers new arrivals, besides using memory, can have a much better delay performance than the one in the Tassiulas. But it also has a complexity of O(N).
Li et al. (See, e.g., the articles, Y. Li, S. Panwar, and H. J. Chao, “Exhaustive Service Matching Algorithms for Input Queued Switches,” Proc. of IEEE HPSR (Phoenix, Ariz.) (April 2004), incorporated herein by reference.) proposed a scheduling algorithm by using exhaustive service matching. The algorithm only has a complexity of O(log N), thus it still scales with increase in the size of a switch.
All these scheduling algorithms assume that variable-size packets are segmented into fixed-size cells after arriving. They are reassembled back into original packets at the output ports. Cells from a packet are switched independently, and a packet can leave the system only when all of its cells are received. These algorithms are referred to as cell-mode scheduling.
On the other hand, Marsan et al. (See, e.g., the article, M. A. Marsan, A. Bianco, P. Giaccone, E. Leonardi, and F. Neri, “Packet-Mode Scheduling in Input-Queued Cell-Based Switches,” IEEE Transactions on Networking, Vol. 10 (October 2002), incorporated herein by reference.) proposed to switch variable-size packets directly. This is referred to as packet mode scheduling. In packet-mode scheduling, the input ports have to deliver typically all the cells from the segmentation of a packet contiguously. Therefore, the reassembly of packets at the output ports may be easier and may require less memory and complexity. They also showed that for some packet size distributions, packet-mode scheduling may have a better delay performance than the cell-mode scheduling. However, the scheduling algorithm proposed, which is called PI-MWM, is a modification of MWM. Therefore, it still has a high computation complexity. Ganjali et al. (See, e.g., the article, Y. Ganjali, A. Keshavarzian, and D. Shah, “Input Queued Switches: Cell Switching vs. Packet Switching,” Proc. of IEEE INFOCOM, (San Francisco, Calif.) (2003), incorporated herein by reference.) show that PI-MWM is stable for any form of re-generative admissible traffic, rather than only Bernoulli traffic.
In view of the foregoing, it would be useful to provide an improved scheduling process which has a low computational complexity, has a simple hardware implementation, can schedule variable-size packets in both packet mode and cell mode, and is stabilized for any admissible Bernoulli traffic.